W2. Sets, Alphabets, Formal Languages, Operations on Languages

Author

Manuel Mazzara

Published

January 29, 2026

1. Summary

1.1 Introduction to Sets

A set is one of the most fundamental concepts in mathematics and computer science. A set is a well-defined collection of distinct objects, called elements or members. When we say “well-defined,” we mean there must be a clear criterion for determining whether something belongs to the set or not—there’s no ambiguity.

Sets can be described in two main ways:

1.1.1 Explicit Enumeration

For finite sets, or when listing is practical, we can describe a set by listing all its elements between curly braces. For example: \[A = \{1, 2, 4, 8\}\]

This notation tells us that $A$ is the set containing exactly the numbers 1, 2, 4, and 8, and no other elements.

For infinite sets or very large finite sets, we sometimes use ellipsis (dots) to indicate the pattern: \[B = \{0, 3, 6, 9, 12, ...\}\]

However, this notation can be ambiguous—different people might interpret the pattern differently.

1.1.2 Set Comprehension (Predicate Notation)

A more reliable way to define a set is to specify the property that characterizes which elements belong to it. This is called set comprehension or defining a set by predicate:

\[B = \{x \mid x \text{ is a non-negative integer multiple of 3}\}\]

Read as: “$B$ is the set of all $x$ such that $x$ is a non-negative integer multiple of 3.”

The vertical bar “$\mid$” means “such that.” This notation is clearer because it explicitly states the rule for membership.

1.2 Basic Set Notation and Relationships

1.2.1 Element Membership

To denote that an element belongs to a set, we use the symbol $\in$ (read as “is an element of” or “is in”): \[2 \in \{1, 2, 3\}\]

This statement is true because 2 is indeed an element of the set $\{1, 2, 3\}$.

To denote that an element is NOT in a set, we use $\notin$: \[4 \notin \{1, 2, 3\}\]

This is true because 4 is not in the set.

1.2.2 The Empty Set

The empty set, denoted by $\emptyset$, is a special set that contains no elements at all. It is unique—there is exactly one empty set. The empty set is a subset of every set (we’ll explain subsets next).

1.2.3 Subsets

A set $A$ is a subset of a set $B$, written $A \subseteq B$, if and only if every element of $A$ is also an element of $B$. In other words, $A$ doesn’t contain anything that $B$ doesn’t.

Example: $\{1, 2\} \subseteq \{1, 2, 3, 4\}$ because every element in $\{1, 2\}$ is also in $\{1, 2, 3, 4\}$.

Important note: Every set is a subset of itself. Also, the empty set $\emptyset$ is a subset of every set.

1.2.4 Set Equality

Two sets are equal if and only if they have exactly the same elements. Mathematically, $A = B$ if and only if $A \subseteq B$ AND $B \subseteq A$. This means:

Every element of $A$ must be in $B$, AND
Every element of $B$ must be in $A$

1.3 Sets Containing Sets

Sets can contain other sets as their elements. For example: \[C = \{\{1, 2, 3\}, \{2, 3, 4, 5\}\}\]

This set $C$ contains exactly two elements, both of which are sets themselves. Note that in this case:

If $A = \{1, 2, 3\}$, then $A \in C$ (because $A$ is an element of $C$)
However, $1 \notin C$ (because the number 1 is not a direct element of $C$; it’s an element of an element of $C$)

The distinction between “$\in$” (element of) and “$\subseteq$” (subset of) is crucial here.

1.4 Operations on Sets

Just as we can add or multiply numbers, we can perform operations on sets to create new sets. The most common operations are:

1.4.1 Union

The union of two sets $A$ and $B$, written $A \cup B$, is the set of all elements that belong to $A$ or $B$ (or both): \[A \cup B = \{x \mid x \in A \lor x \in B\}\]

Here, “$\lor$” represents the logical “or.”

Example: If $A = \{1, 2, 3\}$ and $B = \{2, 3, 4\}$, then $A \cup B = \{1, 2, 3, 4\}$. Notice that even though 2 and 3 appear in both sets, we list them only once in the union.

1.4.2 Intersection

The intersection of two sets $A$ and $B$, written $A \cap B$, is the set of all elements that belong to both $A$ and $B$: \[A \cap B = \{x \mid x \in A \land x \in B\}\]

Here, “$\land$” represents the logical “and.”

Example: If $A = \{1, 2, 3\}$ and $B = \{2, 3, 4\}$, then $A \cap B = \{2, 3\}$. These are the only elements in both sets.

1.4.3 Difference

The difference of two sets $A$ and $B$, written $A \setminus B$ (sometimes $A - B$), is the set of elements in $A$ but not in $B$: \[A \setminus B = \{x \mid x \in A \land x \notin B\}\]

Example: If $A = \{1, 2, 3\}$ and $B = \{2, 3, 4\}$, then $A \setminus B = \{1\}$. This includes only the elements of $A$ that are not in $B$.

1.4.4 Union of Many Sets

We can generalize the union operation to any number of sets. If we have sets $A_0, A_1, A_2, ...$ (possibly infinitely many), their union is denoted:

\[\bigcup_{i=0}^{\infty} A_i\]

or equivalently:

\[\bigcup \{A_i \mid i \ge 0\}\]

This represents the set of all elements that belong to at least one of these sets.

1.5 Power Sets

Given any set $A$, we can form a new set consisting of all possible subsets of $A$. This is called the power set of $A$, denoted $\mathcal{P}(A)$ or sometimes $2^A$.

Example: The power set of $\{a, b, c\}$ is: \[\mathcal{P}(\{a, b, c\}) = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}\]

This set has $2^3 = 8$ elements. In general, if $A$ has $n$ elements, then $\mathcal{P}(A)$ has exactly $2^n$ elements.

Why is it called $2^A$? Because the notation suggests: “the set of all subsets” can be thought of as $2$ choices (include or exclude) for each of the $n$ elements, giving $2^n$ total subsets.

1.6 Alphabets and Strings

An alphabet is a finite set of symbols. We typically denote alphabets with the Greek letter $\Sigma$. For instance:

$\Sigma = \{0, 1\}$ (binary alphabet)
$\Sigma = \{a, b, c, ..., z\}$ (the Roman alphabet)
$\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ (digits)

A string (also called a word or sequence) over an alphabet is a finite sequence of symbols from that alphabet. Repetitions are allowed.

Examples over $\Sigma = \{0, 1\}$:

$010$ is a string (length 3)
$11100011$ is a string (length 8)
$1$ is a string (length 1)

The length of a string $x$, denoted $|x|$, is the number of symbols in the string.

The empty string, denoted $\epsilon$ (the Greek letter epsilon) or sometimes $\lambda$, is the unique string with zero symbols. By definition, $|\epsilon| = 0$.

1.7 The Set of All Strings

Given an alphabet $\Sigma$, the set of all strings over $\Sigma$ (including the empty string) is denoted $\Sigma^*$. This is an infinite set (unless $\Sigma$ is empty).

Example: For $\Sigma = \{0, 1\}$: \[\Sigma^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, ...\}\]

The strings are typically listed in order of length: first strings of length 0, then length 1, then length 2, etc.

1.8 String Concatenation

Just as we can add numbers, we can concatenate strings. If $x$ and $y$ are two strings, their concatenation, written $xy$ (or sometimes $x \cdot y$), is the string formed by writing the symbols of $x$ followed by the symbols of $y$.

Example:

$x = "ab"$
$y = "bab"$
$xy = "abbab"$

Important properties of concatenation:

Associativity: $(xy)z = x(yz)$ for all strings. The order of grouping doesn’t matter.
Non-commutativity: In general, $xy \neq yx$. The order matters!
Identity element: $x\epsilon = \epsilon x = x$. Concatenating with the empty string leaves the string unchanged.

We use exponential notation to represent repeated concatenation: $a^2 = aa$, $a^3 = aaa$, etc.

1.9 Formal Languages

A language is a set of strings over an alphabet. More precisely, a language $L$ over an alphabet $\Sigma$ is any subset of $\Sigma^*$:

\[L \subseteq \Sigma^*\]

Languages can be finite or infinite. Here are some examples:

Over $\Sigma = \{0, 1\}$: The set of all 8-bit binary strings is a language: $L = \{x \in \{0,1\}^* : |x| = 8\}$
Over $\Sigma = \{0, 1\}$: The set of all strings that start with 0 is a language: $L = \{0x : x \in \Sigma^*\}$
Over $\Sigma = \{a, b, c, ..., z\}$: English words form a language
Over $\Sigma = \{0, 1, 2, ..., 9\}$: The set of decimal numbers is a language

The reason “language” is such a broad term is because it captures both natural languages (like English) and formal constructs (like sets of binary strings or programming language syntax).

1.10 Operations on Languages

Since a language is a set, all set operations apply to languages. Additionally, because languages consist of strings, we can use string operations to define new languages.

1.10.1 Set Operations on Languages

The fundamental operations are:

Union: $L_1 \cup L_2 = \{s : s \in L_1 \lor s \in L_2\}$ — strings in either language
Intersection: $L_1 \cap L_2 = \{s : s \in L_1 \land s \in L_2\}$ — strings in both languages
Difference: $L_1 \setminus L_2 = \{s : s \in L_1 \land s \notin L_2\}$ — strings in $L_1$ but not $L_2$
Complement: $\overline{L} = \Sigma^* \setminus L = \{x \in \Sigma^* : x \notin L\}$ — all strings over $\Sigma$ not in $L$

1.10.2 Concatenation of Languages

If $L_1$ and $L_2$ are languages over the same alphabet $\Sigma$, their concatenation is:

\[L_1L_2 = \{xy : x \in L_1, y \in L_2\}\]

This is the set of all strings formed by taking a string from $L_1$ and concatenating it with a string from $L_2$.

Example: If $L_1 = \{a, aa\}$ and $L_2 = \{\epsilon, b, ab\}$, then: \[L_1L_2 = \{a, ab, aab, aa, aab, aaab\}\]

Note that concatenation of languages is not commutative: generally $L_1L_2 \neq L_2L_1$.

Also, there’s an interesting property: if $\epsilon \in L_1$, then $L_1 \cdot L_2 \subseteq L_1L_2$ doesn’t necessarily hold in both directions.

1.10.3 Power of a Language

The power of a language is obtained by concatenating the language with itself. For a positive integer $n$:

\[L^n = \underbrace{L \cdot L \cdot ... \cdot L}_{n \text{ times}}\]

We define $L^0 = \{\epsilon\}$ — a language containing only the empty string.

Example: If $L = \{a, b\}$, then:

$L^1 = \{a, b\}$
$L^2 = \{aa, ab, ba, bb\}$
$L^3 = \{aaa, aab, aba, abb, baa, bab, bba, bbb\}$

When working with an alphabet $\Sigma$, the power $\Sigma^k$ represents all strings of length exactly $k$: \[\Sigma^k = \{x \in \Sigma^* : |x| = k\}\]

1.10.4 The Kleene Star (Kleene Closure)

The Kleene star is one of the most important operations in formal language theory. For a language $L$, the Kleene star (or Kleene closure) of $L$, written $L^*$, is defined as:

\[L^* = \{x_1x_2...x_n : n \in \mathbb{N}, x_1, x_2, ..., x_n \in L\} = \bigcup_{n \in \mathbb{N}} L^n\]

This definition can seem complex, so let’s break it down:

We take zero or more strings from $L$
We concatenate them together
$L^*$ is the set of ALL possible results of such concatenations
The “zero or more” part means that the empty string $\epsilon$ is always in $L^*$ (when we take zero strings and concatenate them, we get $\epsilon$)

Example: If $L = \{a\}$, then: \[L^* = \{\epsilon, a, aa, aaa, aaaa, ...\}\]

This is all strings consisting of the symbol $a$ repeated any number of times (including zero times, giving $\epsilon$).

Another example: If $L = \{ab\}$, then: \[L^* = \{\epsilon, ab, abab, ababab, ababab, ...\}\]

The Kleene star is called a “closure” because applying it to any set gives you a closed set under the concatenation operation—if you take any two strings from $L^*$ and concatenate them, you get another string in $L^*$.

1.10.5 The Kleene Plus

A related operation is the Kleene plus, written $L^+$, which is like the Kleene star but excludes the empty string:

\[L^+ = L^* \setminus \{\epsilon\} = \bigcup_{n=1}^{\infty} L^n\]

This represents one or more concatenations of strings from $L$ (but at least one is required).

Example: If $L = \{a\}$, then: \[L^+ = \{a, aa, aaa, aaaa, ...\}\]

Note the difference: $L^*$ includes $\epsilon$, but $L^+$ does not.

1.11 Notation Summary for Special Cases

For an alphabet $\Sigma$ and a string $a$:

$a^0 = \epsilon$ (by convention, any string to the power 0 is the empty string)
$a^k = \underbrace{aa...a}_{k \text{ times}}$ (concatenating $a$ with itself $k$ times)
$\Sigma^k = \{x \in \Sigma^* : |x| = k\}$ (all strings of length exactly $k$ over $\Sigma$)
$\Sigma^* = \bigcup_{k=0}^{\infty} \Sigma^k$ (all strings of any length over $\Sigma$)
$\Sigma^+ = \Sigma^* \setminus \{\epsilon\}$ (all non-empty strings over $\Sigma$)

2. Definitions

Alphabet: A finite set of symbols, typically denoted $\Sigma$. Examples include $\{0, 1\}$, $\{a, b, c, ..., z\}$, or any finite collection of distinct symbols.
String (also word or sequence): A finite sequence of symbols from an alphabet, where repetitions are allowed. The length of a string $x$, denoted $|x|$, is the number of symbols it contains.
Empty String: The unique string containing zero symbols, denoted $\epsilon$ (epsilon). By definition, $|\epsilon| = 0$.
Set: A well-defined collection of distinct objects called elements. Sets are determined by the property of their elements: for any object, it either is or is not an element of the set (no ambiguity).
Element: An object belonging to a set. We write $x \in A$ to denote that $x$ is an element of set $A$, and $x \notin A$ to denote that it is not.
Subset: Set $A$ is a subset of set $B$, written $A \subseteq B$, if every element of $A$ is also an element of $B$. Every set is a subset of itself, and the empty set is a subset of every set.
Empty Set: The unique set containing no elements, denoted $\emptyset$. The empty set is a subset of every set.
Set Equality: Two sets $A$ and $B$ are equal (written $A = B$) if and only if they have exactly the same elements, i.e., $A \subseteq B$ and $B \subseteq A$.
Union of Sets: The union of sets $A$ and $B$, denoted $A \cup B$, is the set of all elements that belong to $A$ or $B$ (or both): $A \cup B = \{x \mid x \in A \lor x \in B\}$.
Intersection of Sets: The intersection of sets $A$ and $B$, denoted $A \cap B$, is the set of all elements that belong to both $A$ and $B$: $A \cap B = \{x \mid x \in A \land x \in B\}$.
Set Difference: The difference of sets $A$ and $B$, denoted $A \setminus B$ or $A - B$, is the set of elements in $A$ but not in $B$: $A \setminus B = \{x \mid x \in A \land x \notin B\}$.
Power Set: The power set of a set $A$, denoted $\mathcal{P}(A)$ or $2^A$, is the set of all subsets of $A$, including the empty set and $A$ itself. If $A$ has $n$ elements, then $\mathcal{P}(A)$ has $2^n$ elements.
Set Comprehension: A method of defining a set by specifying a property that characterizes its elements: $A = \{x \mid P(x)\}$ means “$A$ is the set of all $x$ such that property $P(x)$ is true.”
Language: A language $L$ over an alphabet $\Sigma$ is a set of strings over $\Sigma$, i.e., any subset of $\Sigma^*$. Languages can be finite or infinite.
$\Sigma^*$: The set of all strings over alphabet $\Sigma$, including the empty string. This is the union of all strings of every possible length: $\Sigma^* = \bigcup_{k=0}^{\infty} \Sigma^k$.
String Concatenation: The operation of joining two strings end-to-end. If $x$ and $y$ are strings, their concatenation $xy$ (or $x \cdot y$) is the string formed by writing the symbols of $x$ followed by the symbols of $y$. Concatenation is associative but not commutative.
Concatenation of Languages: For languages $L_1$ and $L_2$, their concatenation is $L_1L_2 = \{xy : x \in L_1, y \in L_2\}$, the set of all strings formed by concatenating a string from $L_1$ with a string from $L_2$.
Power of a Language: The $n$-th power of a language $L$, denoted $L^n$, is the concatenation of $L$ with itself $n$ times. By convention, $L^0 = \{\epsilon\}$.
Kleene Star (Kleene Closure): For a language $L$, the Kleene star $L^*$ is the set of all strings obtained by concatenating zero or more strings from $L$: $L^* = \bigcup_{n=0}^{\infty} L^n$. This always includes the empty string $\epsilon$.
Kleene Plus: For a language $L$, the Kleene plus $L^+$ is the set of all strings obtained by concatenating one or more strings from $L$: $L^+ = L^* \setminus \{\epsilon\} = \bigcup_{n=1}^{\infty} L^n$. This excludes the empty string.
Complement of a Language: For a language $L$ over alphabet $\Sigma$, the complement $\overline{L}$ (or $L^c$) is the set of all strings over $\Sigma$ that are not in $L$: $\overline{L} = \Sigma^* \setminus L = \{x \in \Sigma^* \mid x \notin L\}$.
Cardinality: The cardinality of a finite set $A$, denoted $|A|$, is the number of elements in $A$. For infinite sets, cardinality refers to the “size” of the set in a more abstract sense.
Free Monoid: The set $\Sigma^*$ with string concatenation as the operation. A monoid is a set with an associative binary operation and an identity element (here, $\epsilon$ is the identity). The term “free” indicates there are no additional constraints on how strings can be combined.

3. Formulas

Set Union: $A \cup B = \{x \mid x \in A \lor x \in B\}$
Set Intersection: $A \cap B = \{x \mid x \in A \land x \in B\}$
Set Difference: $A \setminus B = \{x \mid x \in A \land x \notin B\}$
Union of Multiple Sets: $\bigcup_{i=0}^{\infty} A_i = \{x \mid x \in A_i \text{ for at least one } i \geq 0\}$
Power Set Cardinality: If $|A| = n$, then $|\mathcal{P}(A)| = 2^n$
String Length: $|x|$ denotes the number of symbols in string $x$; $|\epsilon| = 0$
String Concatenation: If $x$ and $y$ are strings, then $xy = $ the string formed by writing symbols of $x$ followed by symbols of $y$
Concatenation Associativity: $(xy)z = x(yz)$ for all strings
Concatenation Identity: $x\epsilon = \epsilon x = x$ for any string $x$
Power of a String: $a^k = \underbrace{aa...a}_{k \text{ times}}$ for $k > 0$; $a^0 = \epsilon$
Language Concatenation: $L_1L_2 = \{xy : x \in L_1, y \in L_2\}$
Power of a Language: $L^n = \{x_1x_2...x_n : x_i \in L \text{ for all } 1 \leq i \leq n\}$; $L^0 = \{\epsilon\}$
Kleene Star: $L^* = \bigcup_{n=0}^{\infty} L^n = \{x_1x_2...x_n \mid n \in \mathbb{N}, x_i \in L\}$
Kleene Plus: $L^+ = L^* \setminus \{\epsilon\} = \bigcup_{n=1}^{\infty} L^n$
Strings of Exact Length: $\Sigma^k = \{x \in \Sigma^* \mid |x| = k\}$
All Strings over Alphabet: $\Sigma^* = \bigcup_{k=0}^{\infty} \Sigma^k$
All Non-empty Strings: $\Sigma^+ = \Sigma^* \setminus \{\epsilon\}$
Language Complement: $\overline{L} = \Sigma^* \setminus L = \{x \in \Sigma^* \mid x \notin L\}$

4. Examples

4.1. Determining Sets from Descriptions (Lab 2, Task 1.1)

Determine the set $D = \{\{x\} \mid x \text{ is a non-negative integer such that } x \le 4\}$.

Click to see the solution

Key Concept: This set consists of singleton sets (sets containing one element). We need to identify which singleton sets are included based on the condition that $x$ must be a non-negative integer at most 4.

Identify the non-negative integers satisfying the condition: We need $x \leq 4$ where $x \geq 0$, so $x \in \{0, 1, 2, 3, 4\}$.
Form singleton sets for each value: For each such $x$, we create a set containing just that element:
- For $x = 0$: $\{0\}$
- For $x = 1$: $\{1\}$
- For $x = 2$: $\{2\}$
- For $x = 3$: $\{3\}$
- For $x = 4$: $\{4\}$
Collect all these singleton sets into $D$: \[D = \{\{0\}, \{1\}, \{2\}, \{3\}, \{4\}\}\]

Answer: $D = \{\{0\}, \{1\}, \{2\}, \{3\}, \{4\}\}$

4.2. Determining Sets from Descriptions (Lab 2, Task 1.2)

Determine the set $E = \{3i + 5j \mid i \text{ and } j \text{ are non-negative integers}\}$.

Click to see the solution

Key Concept: This set consists of all non-negative integer linear combinations of 3 and 5. We need to determine which non-negative integers can be expressed as $3i + 5j$.

List some elements: Let’s systematically find values by trying different values of $i$ and $j$:
- $i=0, j=0$: $3(0) + 5(0) = 0$
- $i=1, j=0$: $3(1) + 5(0) = 3$
- $i=0, j=1$: $3(0) + 5(1) = 5$
- $i=2, j=0$: $3(2) + 5(0) = 6$
- $i=1, j=1$: $3(1) + 5(1) = 8$
- $i=3, j=0$: $3(3) + 5(0) = 9$
- $i=0, j=2$: $3(0) + 5(2) = 10$
- And so on…
Identify which integers CAN be represented: It can be shown that every non-negative integer except 1, 2, 4, and 7 can be represented as $3i + 5j$. This is related to the Frobenius coin problem: with denominations of 3 and 5, the largest amount that cannot be made is $3 \cdot 5 - 3 - 5 = 7$.
Write the set explicitly: \[E = \{0, 3, 5, 6, 8, 9, 10, 11, 12, ...\} = \{n \in \mathbb{Z}^+ \cup \{0\} \mid n \neq 1, 2, 4, 7\}\]

Answer: $E = \{0, 3, 5, 6, 8, 9, 10, 11, 12, ...\}$ (all non-negative integers except 1, 2, 4, and 7)

4.3. Set Equality (Lab 2, Task 1.3)

Are the sets $\{0, 1\}$ and $\{1, 0\}$ equal?

Click to see the solution

Key Concept: Sets are determined solely by their elements, not by the order in which elements are listed.

Identify the elements of the first set: $\{0, 1\}$ contains the elements 0 and 1.
Identify the elements of the second set: $\{1, 0\}$ contains the elements 1 and 0.
Compare: Both sets contain exactly the same elements: 0 and 1.
Verify set equality: Two sets are equal if and only if they have exactly the same elements. Since both $\{0, 1\}$ and $\{1, 0\}$ contain the same elements (0 and 1), they are equal.

Answer: Yes, $\{0, 1\} = \{1, 0\}$. Order does not matter in sets.

4.4. Set Equality and Duplicates (Lab 2, Task 1.4)

Are the sets $\{0, 1, 2, 1, 0\}$ and $\{1, 1, 1, 1, 0, 2, 2\}$ equal?

Click to see the solution

Key Concept: In set notation, duplicate elements are listed only once. A set is determined by which distinct elements it contains.

Identify the distinct elements in the first set: $\{0, 1, 2, 1, 0\}$ contains 0 (repeated), 1 (repeated), and 2 (listed once). The distinct elements are: $\{0, 1, 2\}$.
Identify the distinct elements in the second set: $\{1, 1, 1, 1, 0, 2, 2\}$ contains 1 (repeated), 0, and 2 (repeated). The distinct elements are: $\{0, 1, 2\}$.
Compare: Both sets have exactly the same distinct elements: 0, 1, and 2.
Conclusion: Since both representations describe the same set, they are equal.

Answer: Yes, $\{0, 1, 2, 1, 0\} = \{1, 1, 1, 1, 0, 2, 2\} = \{0, 1, 2\}$.

4.5. Power Set Construction (Lab 2, Task 2.1)

Construct the power set of $\{a, b\}$.

Click to see the solution

Key Concept: The power set consists of ALL subsets, including the empty set and the set itself.

List all possible subsets of $\{a, b\}$:
- The subset containing no elements: $\emptyset$
- Subsets containing one element: $\{a\}$, $\{b\}$
- Subsets containing two elements: $\{a, b\}$
Verify completeness: For each element, we have a choice to include it or exclude it:
- Exclude $a$ and $b$: $\emptyset$
- Include only $a$: $\{a\}$
- Include only $b$: $\{b\}$
- Include both $a$ and $b$: $\{a, b\}$
Count: We have 2 elements, so we expect $2^2 = 4$ subsets. We listed 4, which is correct.

Answer: $\mathcal{P}(\{a, b\}) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}$

4.6. Power Set Construction (Lab 2, Task 2.2)

Construct the power set of $\{0, 1\} \cup \{1, 2\}$.

Click to see the solution

Key Concept: First, simplify the set by computing the union, then find all subsets.

Compute the union: $\{0, 1\} \cup \{1, 2\} = \{0, 1, 2\}$.
Find all subsets of $\{0, 1, 2\}$:
- Zero elements: $\emptyset$
- One element: $\{0\}$, $\{1\}$, $\{2\}$
- Two elements: $\{0, 1\}$, $\{0, 2\}$, $\{1, 2\}$
- Three elements: $\{0, 1, 2\}$
Verify count: With 3 elements, we expect $2^3 = 8$ subsets. We have 8, which is correct.

Answer: $\mathcal{P}(\{0, 1, 2\}) = \{\emptyset, \{0\}, \{1\}, \{2\}, \{0, 1\}, \{0, 2\}, \{1, 2\}, \{0, 1, 2\}\}$

4.7. Power Set Construction (Lab 2, Task 2.3)

Construct the power set of $\{z\}$.

Click to see the solution

Key Concept: A singleton set (set with one element) has a power set with $2^1 = 2$ subsets.

Identify all subsets of $\{z\}$:
- The empty set: $\emptyset$
- The set containing $z$: $\{z\}$

Answer: $\mathcal{P}(\{z\}) = \{\emptyset, \{z\}\}$

4.8. Set Operations and Power Sets (Lab 2, Task 2.4)

Construct the power set of $\{0, 1, 2, 3, 4\} \cap \{1, 3, 5, a\}$.

Click to see the solution

Key Concept: First find the intersection, then construct its power set.

Compute the intersection: We need elements that are in BOTH sets.
- Is 0 in both? $0 \in \{0, 1, 2, 3, 4\}$ but $0 \notin \{1, 3, 5, a\}$. No.
- Is 1 in both? Yes.
- Is 2 in both? No.
- Is 3 in both? Yes.
- Is 4 in both? No.
- Is 5 in both? No.
- Is $a$ in both? No.
Therefore: $\{0, 1, 2, 3, 4\} \cap \{1, 3, 5, a\} = \{1, 3\}$
Find the power set of $\{1, 3\}$:
- $\emptyset$
- $\{1\}$
- $\{3\}$
- $\{1, 3\}$

Answer: $\mathcal{P}(\{1, 3\}) = \{\emptyset, \{1\}, \{3\}, \{1, 3\}\}$

4.9. Set Operations and Power Sets (Lab 2, Task 2.5)

Construct the power set of $\{0, 1, 2, 3\} \setminus \{1, 3, 5, a\}$.

Click to see the solution

Key Concept: First find the set difference, then construct its power set.

Compute the set difference: We need elements in the first set but NOT in the second.
- Is 0 in the first set but not the second? $0 \in \{0, 1, 2, 3\}$ and $0 \notin \{1, 3, 5, a\}$. Yes.
- Is 1 in the first but not the second? $1 \in \{0, 1, 2, 3\}$ but $1 \in \{1, 3, 5, a\}$. No.
- Is 2 in the first but not the second? Yes.
- Is 3 in the first but not the second? No.
Therefore: $\{0, 1, 2, 3\} \setminus \{1, 3, 5, a\} = \{0, 2\}$
Find the power set of $\{0, 2\}$:
- $\emptyset$
- $\{0\}$
- $\{2\}$
- $\{0, 2\}$

Answer: $\mathcal{P}(\{0, 2\}) = \{\emptyset, \{0\}, \{2\}, \{0, 2\}\}$

4.10. Power Set of Empty Set (Lab 2, Task 2.6)

Construct the power set of $\emptyset$.

Click to see the solution

Key Concept: The power set of the empty set contains the empty set as its only element.

Find all subsets of $\emptyset$: The only subset of the empty set is the empty set itself.
Verify count: With 0 elements, we expect $2^0 = 1$ subset. We have 1, which is correct.

Answer: $\mathcal{P}(\emptyset) = \{\emptyset\}$

4.11. Formal Language Basics (Lab 2, Task 2.7)

Determine $\Sigma^0$ for any alphabet $\Sigma$.

Click to see the solution

Key Concept: $\Sigma^k$ represents all strings of length exactly $k$ over the alphabet $\Sigma$. So $\Sigma^0$ contains all strings of length 0.

Find all strings of length 0: There is exactly one string of length 0: the empty string $\epsilon$.
Therefore: $\Sigma^0 = \{\epsilon\}$

Answer: $\Sigma^0 = \{\epsilon\}$ for any alphabet $\Sigma$.

4.12. All Strings of Exact Length (Lab 2, Task 2.8)

Determine $\Sigma^4$ for $\Sigma = \{0, 1\}$.

Click to see the solution

Key Concept: $\Sigma^4$ consists of all strings of length exactly 4 over the binary alphabet.

Count the number of strings: Each position can be filled with either 0 or 1, and there are 4 positions. This gives $2^4 = 16$ strings.
List all strings of length 4 over $\{0, 1\}$:
- Starting with 00: $0000, 0001, 0010, 0011$
- Starting with 01: $0100, 0101, 0110, 0111$
- Starting with 10: $1000, 1001, 1010, 1011$
- Starting with 11: $1100, 1101, 1110, 1111$

Answer: $\Sigma^4 = \{0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111\}$

4.13. Power Set of an Alphabet (Lab 2, Task 2.9)

Determine $\mathcal{P}(\Sigma)$ for $\Sigma = \{0, 1\}$.

Click to see the solution

Key Concept: $\mathcal{P}(\Sigma)$ is the power set of the alphabet itself, containing all subsets of $\Sigma$.

List all subsets of $\{0, 1\}$:
- The empty subset: $\emptyset$
- Subsets with one element: $\{0\}$, $\{1\}$
- The subset with both elements: $\{0, 1\}$
Verify count: With 2 elements, we expect $2^2 = 4$ subsets. We have 4, which is correct.

Answer: $\mathcal{P}(\Sigma) = \{\emptyset, \{0\}, \{1\}, \{0, 1\}\}$

4.14. Power Set of All Strings (Lab 2, Task 2.10)

Determine $\mathcal{P}(\Sigma^*)$ for $\Sigma = \{0, 1\}$.

Click to see the solution

Key Concept: $\Sigma^*$ is an infinite set of all strings over $\Sigma$. Its power set $\mathcal{P}(\Sigma^*)$ is the set of all subsets of $\Sigma^*$.

Understand the structure: $\Sigma^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, ...\}$ is an infinite set containing all possible finite strings.
Determine $\mathcal{P}(\Sigma^*)$: This is the power set of an infinite set, so it is also infinite (in fact, it has a higher level of infinity than $\Sigma^*$).
Examples of elements in $\mathcal{P}(\Sigma^*)$:
- $\emptyset$ (the empty language)
- $\{\epsilon\}$ (language containing only empty string)
- $\{0, 1\}$ (language containing only two single-symbol strings)
- $\Sigma^*$ (the language of all strings)
- The set of all strings starting with 0
- The set of all strings with even length
- Any other subset of $\Sigma^*$

Answer: $\mathcal{P}(\Sigma^*)$ is the set of all subsets of $\Sigma^*$ (all possible languages over $\Sigma$). It is an uncountably infinite set with $2^{\infty}$ elements.

4.15. Find Alphabets for Languages (Lab 2, Task 3.1)

Find a possible alphabet for the language $L = \{oh, ouch, ugh\}$.

Click to see the solution

Key Concept: An alphabet must contain all distinct symbols that appear in the strings of the language.

List all strings in the language: $L = \{oh, ouch, ugh\}$
Identify all distinct characters that appear:
- In “oh”: characters $o$ and $h$
- In “ouch”: characters $o$, $u$, $c$, $h$
- In “ugh”: characters $u$, $g$, $h$
Collect all distinct characters: $\{o, u, h, c, g\}$
Verify: Every string in the language consists only of characters from this set.

Answer: A possible alphabet is $\Sigma = \{o, u, h, c, g\}$ (or any superset of this).

4.16. Find Alphabets for Languages (Lab 2, Task 3.2)

Find a possible alphabet for the language $L = \{apple, pear, 4711\}$.

Click to see the solution

Key Concept: The alphabet must include all characters appearing in any string of the language.

Identify all distinct characters:
- In “apple”: $a, p, l, e$
- In “pear”: $p, e, a, r$
- In “4711”: $4, 7, 1$
Collect all distinct characters: $\{a, p, p, l, e, p, e, a, r, 4, 7, 1, 1\}$

Removing duplicates: $\{a, p, l, e, r, 4, 7, 1\}$

Answer: A possible alphabet is $\Sigma = \{a, p, l, e, r, 4, 7, 1\}$ (or any superset containing at least these characters).

4.17. Find Alphabets for Languages (Lab 2, Task 3.3)

Find a possible alphabet for the language of all binary strings.

Click to see the solution

Key Concept: Binary strings use only two symbols: 0 and 1.

Identify the symbols needed: Binary strings consist of sequences of 0’s and 1’s.

Answer: $\Sigma = \{0, 1\}$

4.18. Kleene Star over Different Alphabets (Lab 2, Task 3.4)

Determine what $\Sigma^*$ produces for $\Sigma = \{0, 1\}$.

Click to see the solution

Key Concept: $\Sigma^*$ is the set of all strings (of any length) over $\Sigma$.

Description: $\Sigma^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, ...\}$
Interpretation: This is the set of all finite binary strings, including the empty string.

Answer: $\{0, 1\}^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, ...\}$ (all binary strings of any length)

4.19. Kleene Star over Different Alphabets (Lab 2, Task 3.5)

Determine what $\Sigma^*$ produces for $\Sigma = \{a\}$.

Click to see the solution

Key Concept: When the alphabet contains a single symbol, $\Sigma^*$ contains all repetitions of that symbol.

List the contents:
- Length 0: $\epsilon$
- Length 1: $a$
- Length 2: $aa$
- Length 3: $aaa$
- And so on…
Expression: $\Sigma^* = \{\epsilon, a, aa, aaa, aaaa, ...\} = \{a^n \mid n \in \mathbb{N}\}$

Answer: $\{a\}^* = \{\epsilon, a, aa, aaa, aaaa, ...\} = \{a^n \mid n \geq 0\}$

4.20. Kleene Star over Empty Alphabet (Lab 2, Task 3.6)

Determine what $\Sigma^*$ produces for $\Sigma = \emptyset$ (the empty alphabet).

Click to see the solution

Key Concept: If we have no symbols available, we can’t form any non-empty strings. We can only form the empty string.

Analyze: Without any symbols in the alphabet, the only string we can form is the empty string (which uses zero symbols).

Answer: $\emptyset^* = \{\epsilon\}$ (only the empty string)

4.21. Determining the Alphabet (Lab 2, Task 4.1)

For the language $L = \Sigma^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, ...\}$, determine the alphabet $\Sigma$.

Click to see the solution

Key Concept: We identify the symbols that appear in the strings of the language.

Observe the strings: The language contains all strings using symbols 0 and 1.
Identify the alphabet: The only symbols appearing are 0 and 1.

Answer: $\Sigma = \{0, 1\}$

4.22. Determining the Alphabet (Lab 2, Task 4.2)

For the language $L = \Sigma^* = \{\epsilon, a, aa, aaa, aaaa, ...\}$, determine the alphabet $\Sigma$.

Click to see the solution

Key Concept: We identify which symbols appear in the language.

Observe: All strings consist only of the symbol $a$ repeated.

Answer: $\Sigma = \{a\}$

4.23. Language Complement (Lab 2, Task 4.3)

Assuming $\Sigma = \{0, 1\}$, construct the complement $\overline{L}$ for $L = \{010, 101, 11\}$.

Click to see the solution

Key Concept: The complement of a language is the set of all strings over $\Sigma$ that are NOT in $L$.

Define the complement: $\overline{L} = \Sigma^* \setminus L = \{x \in \{0,1\}^* : x \notin L\}$
Description: $\overline{L}$ consists of all binary strings except 010, 101, and 11. This includes:
- $\epsilon$ (the empty string)
- All single-symbol strings: $0, 1$
- All two-symbol strings except nothing (since we excluded three-symbol strings, not two-symbol): $00, 01, 10$
- All three-symbol strings except 010 and 101: $000, 001, 011, 100, 110, 111$
- All four-symbol strings and beyond
Explicit representation: \[\overline{L} = \{\epsilon, 0, 1, 00, 01, 10, 000, 001, 011, 100, 110, 111, 0000, ...\} \setminus \{010, 101, 11\}\]

Answer: $\overline{L} = \{x \in \{0,1\}^* : x \notin \{010, 101, 11\}\}$ (all binary strings except 010, 101, and 11)

4.24. Language Complement (Lab 2, Task 4.4)

Assuming $\Sigma = \{0, 1\}$, construct the complement $\overline{L}$ for $L = \Sigma^* \setminus \{110\}$.

Click to see the solution

Key Concept: We need to find the complement of a language that is “all strings except 110”.

Understand the original language: $L = ^* {110} = $ all binary strings except the string 110.
Find the complement: \[\overline{L} = \Sigma^* \setminus L = \Sigma^* \setminus (\Sigma^* \setminus \{110\})\]

By set theory, $\Sigma^* \setminus (\Sigma^* \setminus \{110\}) = \{110\}$
Verify: The strings in $\Sigma^*$ are partitioned into two groups:
- Those in $L$ (all strings except 110)
- Those not in $L$ (which is only 110)
So the complement of $L$ is exactly the set of strings not in $L$, which is $\{110\}$.

Answer: $\overline{L} = \{110\}$

4.25. Power Set Difference (Lab 2, Task 4.5)

Determine the set $\mathcal{P}(\{a, b\}) \setminus \mathcal{P}(\{a, c\})$.

Click to see the solution

Key Concept: Find the power sets first, then compute their difference.

Compute $\mathcal{P}(\{a, b\})$: \[\mathcal{P}(\{a, b\}) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}\]
Compute $\mathcal{P}(\{a, c\})$: \[\mathcal{P}(\{a, c\}) = \{\emptyset, \{a\}, \{c\}, \{a, c\}\}\]
Compute the difference: We need elements in the first set but not in the second.
- Is $\emptyset$ in both? Yes. Not in difference.
- Is $\{a\}$ in both? Yes. Not in difference.
- Is $\{b\}$ in the first? Yes. Is $\{b\}$ in the second? No. Include it.
- Is $\{a, b\}$ in the first? Yes. Is $\{a, b\}$ in the second? No. Include it.
Result: \[\mathcal{P}(\{a, b\}) \setminus \mathcal{P}(\{a, c\}) = \{\{b\}, \{a, b\}\}\]

Answer: $\{\{b\}, \{a, b\}\}$

4.26. Set Comprehension (Lab 2, Task 4.6)

Determine the set $\{x \mid x, y \in \mathbb{N} \land \exists y : y < 10 \land (y + 2 = x)\}$ where $\mathbb{N}$ is the set of all non-negative integers.

Click to see the solution

Key Concept: This notation describes values of $x$ where there exists some $y < 10$ such that $x = y + 2$.

Interpret the condition: We need to find all non-negative integers $x$ such that there exists a non-negative integer $y$ with $y < 10$ and $y + 2 = x$.
Find all possible values: Since $y < 10$, we have $y \in \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$.
- If $y = 0$: $x = 0 + 2 = 2$
- If $y = 1$: $x = 1 + 2 = 3$
- If $y = 2$: $x = 2 + 2 = 4$
- …
- If $y = 9$: $x = 9 + 2 = 11$
Result: $x \in \{2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}$

Answer: $\{2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}$

4.27. Language Concatenation (Lab 2, Task 5.1)

Let $L = \{a^i : i \geq 0\} = \{\epsilon, a, aa, aaa, ...\}$ be a language over $\Sigma = \{a, b\}$. Find $\bar{L}$ and $L^*$.

Click to see the solution

Key Concept: $L$ consists of the empty string and all strings of consecutive $a$’s (with no $b$’s). We need to find its complement and its Kleene star.

(a) Finding $\bar{L}$ (the complement):

Understand $L$: $L = \{\epsilon, a, aa, aaa, aaaa, ...\}$ — strings consisting of zero or more $a$’s only.
Define the complement: $\bar{L} = \Sigma^* \setminus L$ — all strings over $\{a, b\}$ that are NOT in $L$.
Characterize strings in $\bar{L}$: These are strings containing at least one $b$ (since the only strings without $b$ are in $L$).
Express as a set: $\bar{L} = \{x \in \{a, b\}^* : x \text{ contains at least one } b\}$

(b) Finding $L^*$ (the Kleene star):

Recall the definition: $L^* = \{x_1x_2...x_n : n \in \mathbb{N}, x_i \in L\}$
Analyze: We concatenate zero or more strings from $L$. Each string in $L$ is of the form $a^i$ for some $i \geq 0$.
Compute the concatenation: If we take strings $a^{i_1}, a^{i_2}, ..., a^{i_k}$ from $L$ and concatenate them: \[a^{i_1} \cdot a^{i_2} \cdot ... \cdot a^{i_k} = a^{i_1 + i_2 + ... + i_k}\]
Determine the result: Since $i_j \geq 0$ for all $j$, the sum $i_1 + i_2 + ... + i_k$ can be any non-negative integer. Therefore: \[L^* = \{\epsilon, a, aa, aaa, aaaa, ...\} = L\]

Since $L$ already contains all strings of the form $a^n$ for $n \geq 0$, we have $L^* = L$.

Answer:

$\bar{L} = \{x \in \{a, b\}^* : x \text{ contains at least one } b\}$
$L^* = \{a^i : i \geq 0\} = L$

4.28. Language Concatenation (Example) (Lab 2, Task 5.2)

Let $L_1 = \{\epsilon, a, aa\}$ and $L_2 = \{aa, aaa\}$ over $\Sigma = \{a, b\}$. Find $L_1L_2$.

Click to see the solution

Key Concept: Language concatenation creates all possible concatenations of a string from $L_1$ with a string from $L_2$.

Identify the elements:
- $L_1 = \{\epsilon, a, aa\}$ (3 elements)
- $L_2 = \{aa, aaa\}$ (2 elements)
Form all concatenations: For each element $x$ in $L_1$ and each element $y$ in $L_2$, form $xy$:
- $\epsilon \cdot aa = aa$
- $\epsilon \cdot aaa = aaa$
- $a \cdot aa = aaa$
- $a \cdot aaa = aaaa$
- $aa \cdot aa = aaaa$
- $aa \cdot aaa = aaaaa$
Collect unique strings: $L_1L_2 = \{aa, aaa, aaaa, aaaaa\}$

Answer: $L_1L_2 = \{aa, aaa, aaaa, aaaaa\}$

4.29. Language Concatenation (Example) (Lab 2, Task 5.3)

Let $L_1 = \{a, a^2, a^4\}$ and $L_2 = \{b^0, b^2, b^3\}$ over $\Sigma = \{a, b\}$. Find $L_1L_2$.

Click to see the solution

Key Concept: First, expand the exponential notation. $a^n$ means $n$ repetitions of $a$, and $b^0 = \epsilon$.

Expand the sets:
- $L_1 = \{a, aa, aaaa\}$
- $L_2 = \{\epsilon, bb, bbb\}$ (since $b^0 = \epsilon$)
Form all concatenations:
- $a \cdot \epsilon = a$
- $a \cdot bb = abb$
- $a \cdot bbb = abbb$
- $aa \cdot \epsilon = aa$
- $aa \cdot bb = aabb$
- $aa \cdot bbb = aabbb$
- $aaaa \cdot \epsilon = aaaa$
- $aaaa \cdot bb = aaaabb$
- $aaaa \cdot bbb = aaaabbb$
Result: \[L_1L_2 = \{a, abb, abbb, aa, aabb, aabbb, aaaa, aaaabb, aaaabbb\}\]

Answer: $\{a, abb, abbb, aa, aabb, aabbb, aaaa, aaaabb, aaaabbb\}$

4.30. Language Power (Lab 2, Task 5.4)

Let $L = \{0, 01, 001\}$. Find $L^2$.

Click to see the solution

Key Concept: $L^2 = L \cdot L$ consists of all concatenations of two strings from $L$.

Identify the elements of $L$: $L = \{0, 01, 001\}$
Form all concatenations of pairs:
- $0 \cdot 0 = 00$
- $0 \cdot 01 = 001$
- $0 \cdot 001 = 0001$
- $01 \cdot 0 = 010$
- $01 \cdot 01 = 0101$
- $01 \cdot 001 = 01001$
- $001 \cdot 0 = 0010$
- $001 \cdot 01 = 00101$
- $001 \cdot 001 = 001001$
Check for duplicates: All concatenations are unique.

Answer: $L^2 = \{00, 001, 0001, 010, 0101, 01001, 0010, 00101, 001001\}$

4.31. Describing Languages in English (Lab 2, Task 5.5)

Describe the language $L = \{a, b\}^*$ over $\Sigma = \{a, b\}$ in plain English.

Click to see the solution

Key Concept: $\{a, b\}^*$ is the Kleene star of the two-element set, meaning all possible concatenations of $a$’s and $b$’s.

Understand the notation: $\{a, b\}^*$ is the set of all strings that can be formed using the symbols $a$ and $b$.
Content:
- The empty string $\epsilon$
- All single-symbol strings: $a, b$
- All two-symbol strings: $aa, ab, ba, bb$
- All three-symbol strings: $aaa, aab, aba, abb, baa, bab, bba, bbb$
- And so on…

Answer: The language of all finite strings over the alphabet $\{a, b\}$, including the empty string. Equivalently: all possible sequences of $a$’s and $b$’s of any length.

4.32. Describing Languages in English (Lab 2, Task 5.6)

Describe the language $L = \{a\}^* \cup \{b\}^*$ over $\Sigma = \{a, b\}$ in plain English.

Click to see the solution

Key Concept: This is the union of two Kleene stars: strings of $a$’s and strings of $b$’s.

Analyze $\{a\}^*$: This is the set of all strings consisting of zero or more $a$’s: $\{\epsilon, a, aa, aaa, ...\}$
Analyze $\{b\}^*$: This is the set of all strings consisting of zero or more $b$’s: $\{\epsilon, b, bb, bbb, ...\}$
Union: $\{a\}^* \cup \{b\}^* = \{\epsilon, a, aa, aaa, ..., b, bb, bbb, ...\}$

Answer: The language consisting of all strings that are either all $a$’s or all $b$’s (including the empty string). In other words: strings containing only $a$’s, or only $b$’s, but not a mix of both.

4.33. Describing Languages in English (Lab 2, Task 5.7)

Describe the language $L = \{a\}^* \cap \{b\}^*$ over $\Sigma = \{a, b\}$ in plain English.

Click to see the solution

Key Concept: The intersection contains only elements that are in BOTH sets.

Identify $\{a\}^*$: All strings of $a$’s (including $\epsilon$)
Identify $\{b\}^*$: All strings of $b$’s (including $\epsilon$)
Find the intersection: What strings are in BOTH sets? A string can be in $\{a\}^*$ only if it contains no $b$’s. A string can be in $\{b\}^*$ only if it contains no $a$’s. The only string that satisfies both conditions is the empty string $\epsilon$.
Result: $L = \{\epsilon\}$

Answer: The language containing only the empty string: $\{\epsilon\}$

4.34. Describing Languages in English (Lab 2, Task 5.8)

Describe the language $L = \{aa\}^* \setminus \{aaaa\}^*$ over $\Sigma = \{a, b\}$ in plain English.

Click to see the solution

Key Concept: We’re taking the difference of two languages related to even repetitions of $a$.

Understand $\{aa\}^*$: Concatenations of the string “aa”: \[\{aa\}^* = \{\epsilon, aa, aaaa, aaaaaa, aaaaaaaa, ...\} = \{a^{2n} : n \geq 0\}\] This is all strings of $a$’s with even length.
Understand $\{aaaa\}^*$: Concatenations of the string “aaaa”: \[\{aaaa\}^* = \{\epsilon, aaaa, aaaaaaaa, aaaaaaaaaaaa, ...\} = \{a^{4n} : n \geq 0\}\] This is all strings of $a$’s with length divisible by 4.
Compute the difference: $\{aa\}^* \setminus \{aaaa\}^*$ consists of strings in the first but not the second.
- Strings in $\{aa\}^*$: even-length strings of $a$’s
- Strings in $\{aaaa\}^*$: 4-divisible-length strings of $a$’s
- Difference: even-length but not 4-divisible
Characterize: These are strings of $a$’s with length $2, 6, 10, 14, 18, ...$ (i.e., length $\equiv 2 \pmod{4}$)

Answer: Strings of $a$’s whose length is even but not divisible by 4. Examples: $aa, aaaaaa, aaaaaaaa, aaaaaaaaaa, ...$

4.35. String Expansion (Lab 2, Task 5.9)

Write out in full: $0^5, 0^31^3, (010)^2, (01)^30, 1^0$.

Click to see the solution

Key Concept: Exponential notation represents repetition of strings.

$0^5$: The symbol 0 repeated 5 times: $00000$
$0^31^3$: The symbol 0 repeated 3 times, followed by the symbol 1 repeated 3 times: $000111$
$(010)^2$: The string “010” repeated 2 times: $010010$
$(01)^30$: The string “01” repeated 3 times, followed by the digit 0 (i.e., $(01)^3 \cdot 0$): $0101010$
$1^0$: Any string to the power 0 is the empty string: $\epsilon$

Answer:

$0^5 = 00000$
$0^31^3 = 000111$
$(010)^2 = 010010$
$(01)^30 = 0101010$
$1^0 = \epsilon$ (empty string)

4.36. Complex Language Operations (Lab 2, Task 6.1)

Perform the following operations on languages over $\Sigma = \{0, 1\}$:

$L_1 = \{0, 1, 00, 11, 000, 111, ...\}$ $L_2 = \{0, 1\}^*$ $L_3 = \{w \mid w \in \Sigma^*, |w| = 1\}$ $L_4 = \{w \mid w \in \Sigma^*, |w| = 2\}$ $L_5 = \{w \mid w \in \Sigma^*, |w| \geq 1\}$

Find: 1. $L_1 \cup L_2$ and $L_3 \cup L_4$ 2. $L_1 \cap L_2$, $L_1 \cap L_3$, $L_1 \cap L_4$, $L_1 \cap L_5$, $L_3 \cap L_4$

Click to see the solution

Key Concept: These are complex operations on languages. Let’s first clarify what each language is.

Clarify the languages:
- $L_1 = \{0, 1, 00, 11, 000, 111, ...\}$ — strings of identical repeated symbols (all 0’s or all 1’s, length ≥ 1)
  
  More formally: $L_1 = \{0^n : n \geq 1\} \cup \{1^n : n \geq 1\}$
- $L_2 = \{0, 1\}^*$ — all binary strings
- $L_3 = \{w \mid |w| = 1\}$ — all strings of length 1: $L_3 = \{0, 1\}$
- $L_4 = \{w \mid |w| = 2\}$ — all strings of length 2: $L_4 = \{00, 01, 10, 11\}$
- $L_5 = \{w \mid |w| \geq 1\}$ — all non-empty strings: $L_5 = \Sigma^* \setminus \{\epsilon\}$

(Part 1a: $L_1 \cup L_2$)

$L_1 \subseteq L_2$ (every string in $L_1$ is also in $L_2$ since $L_1$ consists of binary strings)
Therefore: $L_1 \cup L_2 = L_2 = \{0, 1\}^*$

(Part 1b: $L_3 \cup L_4$)

$L_3 = \{0, 1\}$ (single-character strings)
$L_4 = \{00, 01, 10, 11\}$ (two-character strings)
$L_3 \cup L_4 = \{0, 1, 00, 01, 10, 11\}$

(Part 2a: $L_1 \cap L_2$)

$L_1 \subseteq L_2$, so $L_1 \cap L_2 = L_1 = \{0^n, 1^n : n \geq 1\}$

(Part 2b: $L_1 \cap L_3$)

$L_1 = \{0, 1, 00, 11, 000, 111, ...\}$
$L_3 = \{0, 1\}$
Strings of length 1 in $L_1$: only $0$ and $1$
Therefore: $L_1 \cap L_3 = \{0, 1\}$

(Part 2c: $L_1 \cap L_4$)

$L_1 = \{0, 1, 00, 11, 000, 111, ...\}$
$L_4 = \{00, 01, 10, 11\}$
Strings of length 2 in $L_1$: only $00$ and $11$ (not mixed strings like $01$ or $10$)
Therefore: $L_1 \cap L_4 = \{00, 11\}$

(Part 2d: $L_1 \cap L_5$)

$L_1$ contains no empty string (all elements have length ≥ 1)
$L_5$ is all non-empty strings
Therefore: $L_1 \cap L_5 = L_1 = \{0^n, 1^n : n \geq 1\}$

(Part 2e: $L_3 \cap L_4$)

$L_3 = \{0, 1\}$ (length 1)
$L_4 = \{00, 01, 10, 11\}$ (length 2)
No string can have both length 1 and length 2
Therefore: $L_3 \cap L_4 = \emptyset$

Answer: 1. $L_1 \cup L_2 = \{0, 1\}^*$ and $L_3 \cup L_4 = \{0, 1, 00, 01, 10, 11\}$ 2. - $L_1 \cap L_2 = \{0^n, 1^n : n \geq 1\}$ - $L_1 \cap L_3 = \{0, 1\}$ - $L_1 \cap L_4 = \{00, 11\}$ - $L_1 \cap L_5 = \{0^n, 1^n : n \geq 1\}$ - $L_3 \cap L_4 = \emptyset$

4.37. Language Set Difference (Lab 2, Task 6.2)

For the same languages from Exercise 5, find: 3. $L_1 \setminus L_2$, $L_1 \setminus L_3$, $L_3 \setminus L_4$, $L_4 \setminus L_5$, $L_5 \setminus L_4$

Click to see the solution

(Part 3a: $L_1 \setminus L_2$)

$L_1 \subseteq L_2$, so there are no elements in $L_1$ that are not in $L_2$
Therefore: $L_1 \setminus L_2 = \emptyset$

(Part 3b: $L_1 \setminus L_3$)

$L_1 = \{0, 1, 00, 11, 000, 111, ...\}$
$L_3 = \{0, 1\}$
Remove strings of length 1 from $L_1$: $L_1 \setminus L_3 = \{00, 11, 000, 111, 0000, 1111, ...\} = \{0^n, 1^n : n \geq 2\}$

(Part 3c: $L_3 \setminus L_4$)

$L_3 = \{0, 1\}$ (length 1)
$L_4 = \{00, 01, 10, 11\}$ (length 2)
No string in $L_3$ is in $L_4$ (different lengths)
Therefore: $L_3 \setminus L_4 = L_3 = \{0, 1\}$

(Part 3d: $L_4 \setminus L_5$)

$L_4 = \{00, 01, 10, 11\}$ (all strings of length 2)
$L_5 = \{w : |w| \geq 1\}$ (all non-empty strings)
All strings in $L_4$ have length ≥ 1, so all are in $L_5$
Therefore: $L_4 \setminus L_5 = \emptyset$

(Part 3e: $L_5 \setminus L_4$)

$L_5 = \{0, 1, 00, 01, 10, 11, 000, 001, ...\}$ (all non-empty strings)
$L_4 = \{00, 01, 10, 11\}$ (all length-2 strings)
Remove length-2 strings from $L_5$: get all non-empty strings except those of length 2
Therefore: $L_5 \setminus L_4 = \{w \in \Sigma^* : |w| \geq 1, |w| \neq 2\} = \{w \in \Sigma^* : |w| = 1\} \cup \{w \in \Sigma^* : |w| \geq 3\}$

Answer: 3. - $L_1 \setminus L_2 = \emptyset$ - $L_1 \setminus L_3 = \{0^n, 1^n : n \geq 2\}$ - $L_3 \setminus L_4 = \{0, 1\}$ - $L_4 \setminus L_5 = \emptyset$ - $L_5 \setminus L_4 = \{w : |w| \neq 2, |w| \geq 1\}$ (all non-empty strings except those of length 2)

4.38. Language Complements (Lab 2, Task 6.3)

For the same languages from Exercise 5, find: 4. $\overline{L_1}$, $\overline{L_2}$, $\overline{L_3}$, $\overline{L_5 \setminus L_4}$

Click to see the solution

(Part 4a: $\overline{L_1}$)

$L_1 = \{0^n, 1^n : n \geq 1\}$ (repetitions of a single symbol)
$\overline{L_1} = \{0, 1\}^* \setminus L_1$ (all strings except pure repetitions)
This includes: $\epsilon$, and all strings containing both 0’s and 1’s or with mixed patterns
More specifically: $\overline{L_1} = \{\epsilon\} \cup \{w : w \text{ contains both 0 and 1}\}$

(Part 4b: $\overline{L_2}$)

$L_2 = \{0, 1\}^*$ (all binary strings)
$\overline{L_2} = \{0, 1\}^* \setminus L_2 = \emptyset$ (complement of the universal language is empty)

(Part 4c: $\overline{L_3}$)

$L_3 = \{0, 1\}$ (strings of length 1)
$\overline{L_3} = \{0, 1\}^* \setminus L_3$ (all strings except 0 and 1)
This is: $\overline{L_3} = \{\epsilon\} \cup \{w : |w| \neq 1\}$ (empty string and strings of length ≠ 1)

(Part 4d: $\overline{L_5 \setminus L_4}$)

From previous exercise: $L_5 \setminus L_4 = \{w : |w| \neq 2, |w| \geq 1\}$ (non-empty strings except length-2)
$\overline{L_5 \setminus L_4} = \{0, 1\}^* \setminus \{w : |w| \neq 2, |w| \geq 1\}$
The complement contains: strings of length 2, or the empty string
Therefore: $\overline{L_5 \setminus L_4} = \{\epsilon\} \cup L_4 = \{\epsilon, 00, 01, 10, 11\}$

Answer: 4. - $\overline{L_1} = \{\epsilon\} \cup \{w : w \text{ contains both 0 and 1}\}$ (empty string or mixed strings) - $\overline{L_2} = \emptyset$ - $\overline{L_3} = \{\epsilon\} \cup \{w : |w| \neq 1\}$ (empty string and non-length-1 strings) - $\overline{L_5 \setminus L_4} = \{\epsilon, 00, 01, 10, 11\}$ (empty string and all length-2 strings)

4.39. Language Concatenation (Lab 2, Task 6.4)

For the same languages from Exercise 5, find: 5. $L_1L_2$, $L_3L_4$, $L_4L_3$

Click to see the solution

(Part 5a: $L_1L_2$)

$L_1 = \{0^n, 1^n : n \geq 1\}$
$L_2 = \{0, 1\}^*$ (all binary strings)
$L_1L_2 = \{xy : x \in L_1, y \in L_2\}$

Analyze: For each string in $L_1$ (a repetition of one symbol) and concatenate with any string in $L_2$ (any binary string)
Examples:
- Take $x = 0 \in L_1$ and $y = 010 \in L_2$: $xy = 0010$
- Take $x = 111 \in L_1$ and $y = 00 \in L_2$: $xy = 11100$
Characterization: Can we get any binary string from $L_1L_2$?
- Take any binary string $w$. We want to show $w \in L_1L_2$
- If $w = \epsilon$, we need $x \in L_1$ and $y \in L_2$ with $xy = \epsilon$. This is impossible since $L_1$ contains no empty string
- If $w$ starts with 0, write $w = 0w'$ where $w'$ is any string. Take $x = 0 \in L_1$ and $y = w' \in L_2$
- If $w$ starts with 1, write $w = 1w'$. Take $x = 1 \in L_1$ and $y = w' \in L_2$
Result: $L_1L_2 = \Sigma^* \setminus \{\epsilon\} = L_5$

(Part 5b: $L_3L_4$)

$L_3 = \{0, 1\}$ (single symbols)
$L_4 = \{00, 01, 10, 11\}$ (two-symbol strings)
$L_3L_4 = \{xy : x \in L_3, y \in L_4\}$

Form all concatenations:
- $0 \cdot 00 = 000$
- $0 \cdot 01 = 001$
- $0 \cdot 10 = 010$
- $0 \cdot 11 = 011$
- $1 \cdot 00 = 100$
- $1 \cdot 01 = 101$
- $1 \cdot 10 = 110$
- $1 \cdot 11 = 111$
Result: $L_3L_4 = \{000, 001, 010, 011, 100, 101, 110, 111\} = \Sigma^3$ (all 3-bit strings)

(Part 5c: $L_4L_3$)

$L_4 = \{00, 01, 10, 11\}$ (two-symbol strings)
$L_3 = \{0, 1\}$ (single symbols)
$L_4L_3 = \{xy : x \in L_4, y \in L_3\}$

Form all concatenations:
- $00 \cdot 0 = 000$
- $00 \cdot 1 = 001$
- $01 \cdot 0 = 010$
- $01 \cdot 1 = 011$
- $10 \cdot 0 = 100$
- $10 \cdot 1 = 101$
- $11 \cdot 0 = 110$
- $11 \cdot 1 = 111$
Result: $L_4L_3 = \{000, 001, 010, 011, 100, 101, 110, 111\} = \Sigma^3$ (all 3-bit strings)

Answer: 5. - $L_1L_2 = \Sigma^+ = \{w : |w| \geq 1\}$ (all non-empty strings) - $L_3L_4 = \Sigma^3 = \{000, 001, 010, 011, 100, 101, 110, 111\}$ - $L_4L_3 = \Sigma^3 = \{000, 001, 010, 011, 100, 101, 110, 111\}$

4.40. Language Kleene Star and Plus (Lab 2, Task 6.5)

For the same languages from Exercise 5, find: 6. $L_2^*$, $L_3^*$, $L_4^*$

Click to see the solution

(Part 6a: $L_2^*$)

$L_2 = \{0, 1\}^*$ (all binary strings)
$L_2^* = $ all concatenations of zero or more strings from $L_2$

Analyze: Any string we concatenate from $L_2$ is already a binary string. Concatenating binary strings gives binary strings.
Verify inclusion both ways:
- Is every string in $L_2^*$ a binary string? Yes, because $L_2$ contains only binary strings, so any concatenation is binary
- Is every binary string in $L_2^*$? Any binary string $w$ can be written as $w = w$ (a single concatenation from $L_2$), so yes
Result: $L_2^* = L_2 = \{0, 1\}^*$

(Part 6b: $L_3^*$)

$L_3 = \{0, 1\}$ (single-character strings)
$L_3^* = $ all concatenations of zero or more strings from $L_3$

Understand: We can concatenate any number of single symbols (0’s and 1’s) to form any binary string
Verify:
- Any concatenation of symbols from $\{0, 1\}$ gives a binary string
- Any binary string is a concatenation of single 0’s and 1’s
- We can concatenate zero symbols to get $\epsilon$
Result: $L_3^* = \{0, 1\}^*$ (all binary strings)

(Part 6c: $L_4^*$)

$L_4 = \{00, 01, 10, 11\}$ (all 2-character strings)
$L_4^* = $ all concatenations of zero or more 2-character strings

Analyze: Each string in $L_4^*$ is formed by concatenating pairs of characters
- Zero concatenations: $\epsilon$
- One concatenation: any 2-character string from $L_4$
- Two concatenations: any 4-character string made of two 2-character parts
- Three concatenations: any 6-character string
- Generally: strings of even length
Key observation: If we concatenate $n$ strings each of length 2, we get a string of length $2n$
Possible lengths: $2 \cdot 0 = 0$ (empty), $2 \cdot 1 = 2$, $2 \cdot 2 = 4$, $2 \cdot 3 = 6$, etc. — all even lengths
Result: $L_4^* = \{w : |w| \text{ is even}\}$ (all binary strings of even length, including the empty string)

Answer: 6. - $L_2^* = \{0, 1\}^*$ (all binary strings) - $L_3^* = \{0, 1\}^*$ (all binary strings) - $L_4^* = \{w \in \{0, 1\}^* : |w| \text{ is even}\}$ (binary strings with even length, including $\epsilon$)

4.41. Alphabet Determination from Language (Tutorial 2, Example 1)

For the language $L = \{x : x \in \Sigma^*, x \text{ starts with 0}\}$, determine the minimal alphabet $\Sigma$.

Click to see the solution

Key Concept: The minimal alphabet must contain all symbols used in the language, but no unnecessary symbols.

Understand the language: The language consists of all strings that start with the digit 0. This could be $0, 00, 01, 000, 001, ...$, etc.
Identify used symbols: Any string starting with 0 must contain the symbol 0. The strings after the initial 0 can contain any symbols from the alphabet.
Minimal alphabet: To have at least one non-zero string in the language (besides just “0”), we need at least one more symbol. The minimal choice is to add just one more symbol, say 1.
Verification: With $\Sigma = \{0, 1\}$, the language $L = \{0x : x \in \Sigma^*\}$ makes sense and matches our description.

Answer: The minimal alphabet is $\Sigma = \{0, 1\}$ or any two-symbol alphabet where one symbol is 0.

4.42. Concatenation Identity Property (Tutorial 2, Concept)

Verify that concatenation is associative and identify the identity element.

Click to see the solution

Key Concept: We need to show $(xy)z = x(yz)$ and find an element $e$ such that $ex = xe = x$.

Associativity:

Define: For strings $x = x_1x_2...x_m$, $y = y_1y_2...y_n$, and $z = z_1z_2...z_p$
Compute $(xy)z$:
- First: $xy = x_1x_2...x_my_1y_2...y_n$
- Then: $(xy)z = x_1x_2...x_my_1y_2...y_nz_1z_2...z_p$
Compute $x(yz)$:
- First: $yz = y_1y_2...y_nz_1z_2...z_p$
- Then: $x(yz) = x_1x_2...x_my_1y_2...y_nz_1z_2...z_p$
Conclusion: Both give the same result, so $(xy)z = x(yz)$.

Identity Element:

Test $\epsilon$ (empty string):
- $\epsilon \cdot x = x$ (no symbols before $x$)
- $x \cdot \epsilon = x$ (no symbols after $x$)
Conclusion: $\epsilon$ is the identity element for string concatenation.

Answer: Concatenation is associative: $(xy)z = x(yz)$. The identity element is $\epsilon$ (empty string): $\epsilon x = x\epsilon = x$ for all strings $x$.